package Ali;

/**
 * 有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。
 *
 * 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。
 n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
 src = 0, dst = 2, k = 1
 输出: 200
 * @author le
 */
public class Test28
{



    public static void main(String[] args)
    {

    }

    private int[][] graph;
    private boolean[] visited;
    private int res = Integer.MAX_VALUE;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        K = Math.min(K, n - 2);

        this.graph = new int[n][n];
        // 建立一个图
        for (int[] flight: flights){
            graph[flight[0]][flight[1]] = flight[2];
        }
        // 定义数组 保存变量是否保存
        this.visited = new boolean[n];

        dfs(src,dst,K+1,0);

        if (res == Integer.MAX_VALUE) {
            return -1;
        }
        return res;


    }

    public void dfs(int src, int dst, int k, int cost){
        if (src == dst){
            res = cost;
            return;
        }

        // 表示走完了
        if (k == 0){
            return;
        }

        for (int i = 0;i < this.graph[src].length;i++){
            if (graph[src][i] > 0){

                if (visited[i]){
                    continue;
                }

                // 剪枝：跳过可能产生较高费用的路径，从而选出最少价格
                if (cost + graph[src][i] > res) {
                    continue;
                }

                visited[i] = true;
                dfs(i,dst,k-1,graph[src][i]+cost);
                visited[i] = false;

            }
        }

    }


}
